
\extitle{1}{因子分解}

字母均表示整数， 除非特殊说明。

\section{整除与带余除法}

\begin{exercise}
      证明：
\begin{enumerate}[(1)]
\item 设 $n^{2}=4 q+r$, 则 $r=0$ 或 1 (即平方数除以 4 余 0 或 1 ).

\item%(2)
若 $n$ 为奇数， 则 $n^{2}=8 q+1, q \in \ZZ$.
\end{enumerate}
\end{exercise}

 \begin{solution}
   \begin{enumerate}
     \item 设 \(n = {2k} + r,r = 0\) 或 $1$,
       则 \({n}^{2} = 4{k}^{2} + {4kr} + {r}^{2} = {4q} + {r}^{2}\).
     \item 奇数$n$可写为 \(n = {4k} + r,r =  \pm  1\),
       则 \({n}^{2} = {16}{k}^{2} + {8kr} + {r}^{2} = {8q} + 1\).
       \qedhere
   \end{enumerate}
 \end{solution}


 \begin{exercise}
   证明： 
\begin{enumerate}[(1)]
\item 若 $b \mid a$ 且 $a \mid b$, 则 $a= \pm b$.

\item%(2)
若 $a\mid b, b\mid  c$, 则 $a \mid c$.

\item%(3)
$a \mid b$ 当且仅当 $a c \mid b c(c \neq 0)$.
\end{enumerate}
\end{exercise}

\begin{solution}
\begin{enumerate}
\item  \(a = {bq} = a{q}_{1}q, 1 = {q}_{1}q,q =  \pm  1\). 
\item  \(c = {bq} = a{q}_{1}q\). 
\item \(b = {aq} \Leftrightarrow  {bc} = {acq}\). \qedhere
\end{enumerate}
\end{solution}

 \begin{exercise}
 设 $b \mid a_{i}$, 证明： $b \mid k_{1} a_{1}+\cdots+k_{s} a_{s}$ (对任意 $k_{i}$ ($i=1, \cdots, s$)).
\end{exercise}

 \begin{exercise}
  设 $a+b=c$. 试证明： 若 $d$ 整除 $a, b, c$ 三者中之二， 则必整除第三者。
\end{exercise}


\begin{exercise}
 
设 $a, m, n$ 为正整数， $n \mid m$, 证明： $\left(a^{n}-1\right) \mid\left(a^{m}-1\right)$.
\end{exercise}

\begin{solution}
  令$m=nd$. 我们有
  \[
    a^m-1=\left( a^n \right)^d-1=(a^n-1)\left( (a^n)^{d-1}+\cdots+a^n+1 \right).
  \]
  故$a^n-1\mid a^m-1$.
\end{solution}

\begin{exercise}
\begin{enumerate}[(1)]
\item 证明： $3 \mid n(4 n+1)(5 n+1)$.


\item%(2)
$a, b$ 满足何条件时， $3 \mid n(a n+1)(b n+1)$ 对任意整数 $n$ 成立?
\end{enumerate}
\end{exercise}


\begin{exercise}
设 $M$ 是一些整数构成的非空集合， 对加、减法封闭 (例如偶数全体。 再如 $4 x+6 y$ 全体 ( $x, y$ 遍历整数)). 设 $d$ 是 $M$ 中最小正整数， 求证： $M$ 恰为 $d$ 的倍数全体。
\end{exercise}
\begin{exercise}
        [$m$ 进 ( $m$-adic) 表示]
          设正整数 $m \geqslant 2$, 则每个正整数 $a$ 可唯一表示为
        \[
        a=a_{0}+a_{1} m+a_{2} m^{2}+\cdots+a_{s} m^{s},
    \]
  其中 $0 \leqslant a_{i} \leqslant m-1, a_{i}$ 和 $s$ 为非负整数。
\end{exercise}

\begin{solution}
  我们对正整数$a$归纳地证明$m$-进制展开的存在性与唯一性。
  若$1\leqslant a<m$, 令$a_0=a$, $a=a_0$就是$m$-进制展开。而若
  \[
    a=a_{0}+a_{1} m+a_{2} m^{2}+\cdots+a_{s} m^{s},
  \]
  为$m$-进制展开，
则
  \[
    a=m(\sum_{i=1}^s a_i m^{i-1}) +a_0.
  \]
是$a$除以$m$的带余除式，
因为$0\leqslant a_0<m$. 
因此$a_0=a, \sum_{i=1}^s a_i m^{i-1}=0$. 这样该$m$-进制展开就是我们开始给的那个。
这就证明了$a$的$m$-进制展开的存在性与唯一性。
现在设$a\geqslant m$. 令$a=mq+a_0$为带余除式。这样$1\leqslant q<a$.
由归纳假设知$q$有$m$-进制展开，比如$q=a_{1} +a_{2} m+\cdots+a_{s} m^{s-1}$.
那么
\[
  a=mq+a_0=m\left( a_{1} +a_{2} m+\cdots+a_{s} m^{s-1} \right) +a_0=a_{0}+a_{1} m+a_{2} m^{2}+\cdots+a_{s} m^{s}.
\]
这就证明了$a$的$m$-进制展开的
的存在性。唯一性的证明与归纳起步中的证明类似，叙述留给你们。


要具体地写出$a$的$m$-进制展开，我们如下写出一串带余除式 (令$q_0=a$)：
  \[
    \begin{aligned}
      q_0&= q_1m+a_0,\\
      q_1&= q_2m+a_1,\\
      & \vdots \\
      q_{s-1}&= q_sm+a_{s-1},\\
      q_s&= 0\cdot m+ a_s=a_s.\quad (\text{$q_{s}<m$ 时算法停止。})
    \end{aligned}
  \]
    进而归纳可知
  \begin{align*}
    a&= q_1m +a_0=(q_2m+a_1)m+a_0 =q_2m^2+a_1m+a_0 \\
    &= \cdots = q_s m^s+\cdots+a_1m+a_0\\
    &= a_{0}+a_{1} m+a_{2} m^{2}+\cdots+a_{s} m^{s}.
    \tag*{\qedhere}
      \end{align*}
\end{solution}

\section{辗转相除与 Bézout 等式}

\begin{exercise}
用辗转相除法求最大公因子及其 Bézout 等式：

\begin{enumerate}[(1)]
\item $d=(648,525)$.

\item%(2)
$d=(70,21,15)$.
\end{enumerate}
\end{exercise}

  \begin{solution}
\begin{enumerate}
    \item 辗转相除得：
      \[
        \begin{aligned}
          648&= 525+123\\
          525&= 123\times 4 +33\\
          123&= 33\times 3+24\\
          33&=  24+9\\
          24&=  9\times 2+6\\
          9&= 6+3\\
          6&= 3\times 2.
        \end{aligned}
      \]
      这样$(648,525)=3$. 且我们有
      \[
        \begin{aligned}
          3&= 9-6=9-(24-9\times 2)=9\times 3-24\\
          &= (33-24)\times 3-24 = 33\times 3-24\times4\\
          &= 33\times 3-(123-33\times 3)\times 4=33\times 15-123\times 4\\
          &= (525-123\times 4)\times 15-123\times 4=525\times 15-123\times 64\\
          &= 525\times 15-(648-525)\times 64=648\times(-64)+525\times 79.
        \end{aligned}
      \]
      这样B\'ezout等式为$3=648\times(-64)+525\times 79.$
    \item 辗转相除得$(70,21)=7$且$70+21\times(-3)=7$.
      易知$(7,15)=1$且$7\times(-2)+15=1$.
      因此$(70,21,15)=1$且
      \[
        1=7\times(-2)+15=(70+21\times(-3))\times(-2)+15=70\times(-2)+21\times 6 +15.
\tag*{\qedhere}
      \]
      \end{enumerate}
  \end{solution}

\begin{exercise}
证明： 
\begin{enumerate}[(1)]
\item $(a, a+k) \mid k$.


\item%(2)
若 $(a, b)=1$, 则 $(a+b, a-b)=1$ 或 2 .

\item%(3)
若 $(a, b)=1, c \mid(a+b)$, 则 $(c, a)=(c, b)=1$.

\item%(4)
若 $(a, b)=1,(a, c)=1$, 则 $(a, b c)=1$.

  
\end{enumerate}
\end{exercise}

\begin{exercise}
证明： 若 $(a, b)=d, a\mid c, b\mid  c$, 则 $a b \mid d c$.
\end{exercise}

\begin{exercise}
证明：若 $(a, c)=1$, 则 $(a, b c)=(a, b)$ (这里设整数 $a, b$ 不全为零).
\end{exercise}

\begin{exercise}
证明： 若 $\left(a_{i}, b_{j}\right)=1$ (对 $\left.1 \leqslant i \leqslant s, 1 \leqslant j \leqslant t\right)$, 则 $\left(a_{1} \cdots a_{s}, b_{1} \cdots b_{i}\right)=1$.
\end{exercise}

\begin{solution}[解答一]
$(a_i,b_j)=1$表明$u_{ij}a_i+v_{ij} b_j=1$, 对某个$u_{ij},v_{ij}\in\ZZ$. 
  这样$u_{ij}a_i\equiv 1\, (\mod b_j)$, 进而$\prod_{i} u_{ij}a_i\equiv 1\,(\mod b_j)$,
  亦即$\prod_{i} u_{ij}a_i+b_jc=1$, 对某个$c\in\ZZ$. 因此$(\prod_i a_i, b_j)=1$.
  既然所有$b_j$与$\prod_i a_i$互素，应用刚才的论证结果有$(\prod_j b_j, \prod_i a_i)=1$.
\end{solution}

\begin{solution}[解答二]
  我们来证明$\prod_j b_j, \prod_i a_i$没有公共的素因子。
  假设有，比如说$p$. $p\mid \prod_i a_i$表明$p\mid a_i$, 对某个$i$;
  类似地，$p\mid \prod_j b_j$表明$p\mid b_j$, 对某个$j$.
  这样$a_i,b_j$不互素，与题设矛盾了。
\end{solution}

\begin{exercise}
设 $a, m, n$ 为正整数， $m>n$, 试求 $d=\left(a^{2^{m}}+1, a^{2^{n}}-1\right)$.
\end{exercise}

\begin{exercise}
设 $m, n$ 为正整数， 试求 $d=\left(2^{m}-1,2^{n}-1\right)$.
\end{exercise}

\begin{solution}
  令$m=qn+r$为带余除式。注意到
  \[
    2^n-1\mid (2^m-1)-(2^r-1)=2^m-2^r=2^r(2^{qn}-1),
  \]
  由(\S1.2, 定理1)知
  \[
    (2^m-1,2^n-1)=(2^n-1,2^r-1).
  \]
令辗转相除求出最大公因子$d=(m,n)$的过程如下 (记$m=r_{-1},n=r_0$)：
  \[
    \begin{aligned}
      m&= nq_0+r_1,\\
      n&= r_1q_1+r_2,\\
      &\vdots\\
      r_{s-2}&= r_{s-1}q_{s-1}+r_s,\\
      r_{s-1}&= r_sq.\quad (s\geqslant 0)
    \end{aligned}
  \]
  那么$d=r_s$. 由刚才的讨论知
  \[
  \begin{aligned}
    (2^m-1,2^n-1)&= (2^n-1,2^{r_1}-1)=(2^{r_1}-1,2^{r_2}-1)\\
        &= \cdots=(2^{r_{s-1}}-1,2^{r_s}-1)\\
        &= 2^{r_s}-1=2^d-1.
      \end{aligned}
\]
这里注意到：由于$r_s\mid r_{s-1}$,  $2^{r_s}-1\mid 2^{r_{s-1}}-1$.
\end{solution}

  \begin{exercise}
  设 $a, b$ 为正整数， $d=(a, b)$, 证明：数集 $S=\{m a+n b\}$ ( $m, n$ 遍历正整数)包含 $d$的大于 $a b$ 的所有倍数。
\end{exercise}

\begin{solution}
  
\end{solution}

\section{唯一析因定理}



\begin{exercise}
证明： $v_{p}(m n)=v_{p}(m)+v_{p}(n), \quad v_{p}\left(m^{k}\right)=k v_{p}(m)$.
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 设$m=(-1)^{\varepsilon(m)}\prod_p p^{v_p(m)}, n=(-1)^{\varepsilon(n)}\prod_p p^{v_p(n)},$
      其中指标$p$跑遍所有正素数。那么
      \[
        mn=(-1)^{\varepsilon(m)+\varepsilon(n)}\prod_p p^{v_p(m)+v_p(n)}.
      \]
      因此，$v_p(mn)=v_p(m)+v_p(n).$
    \item 由(1)知 
      \[
        v_p(m^k)=\underbrace{v_p(m)+\cdots+v_p(m)}_{\text{$k$个}}=k v_p(m).
\tag*{\qedhere}
      \]
  \end{enumerate}
\end{solution}

\begin{exercise}
设 $m, n$ 为非零整数。 试不用算术定理直接证明： $m n=(m, n)[m, n]$.
\end{exercise}

\begin{exercise}
证明：
\begin{enumerate}[(1)]
\item 设 $a, b$ 为正整数， $(a, b)=d$, 则 $\left[\frac{a}{d}, \frac{b}{d}\right]=\frac{[a, b]}{d}$.


\item%(2)
$[a, b, c]=[[a, b], c]$ 对任意整数成立。

\item%(3)
$\left[n_{1}, \cdots, n_{s-1}, n_{s}\right]=\left[\left[n_{1}, \cdots, n_{s-1}\right], n_{s}\right]$ 对任意整数 $n_{1}, \cdots, n_{s-1}, n$, 成立。
\end{enumerate}
\end{exercise}

\begin{exercise}
设正整数 $a, b$ 满足 $a+b=57,[a, b]=680$, 求 $a, b$.
\end{exercise}

\begin{solution}
  令$d=(a,b)$. 那么$d\mid a+b=57, d\mid [a,b]=680$. 从而$d\mid (57,680)=1.$
  因此$d=1$. 这样$ab=(a,b)[a,b]=680.$
  由$a+b=57,ab=680$可知$a,b$为$x^2-57x+680=0$的两个根。
  解之得$(a,b)=(17,40)$或$(40,17)$.
\end{solution}

\begin{exercise}
设 $a, b, c$ 为正整数， 证明：
\[
  [a, b, c]=\frac{a b c(a, b, c)}{(a, b)(b, c)(c, a)}.
\]
\end{exercise}

\begin{solution}
  等号两边都是正整数，只用证明：对任意的素数$p$, 
\[
  v_p([a, b, c]) = v_p\left(\frac{a b c(a, b, c)}{(a, b)(b, c)(c, a)}\right).
\]
由于左右的表达式都是关于  $a,b,c$ 轮换对称，可设
\[
  r=v_p(a)\geqslant s=v_p(b)\geqslant t=v_p(c).
\]
这样
\[
  \begin{aligned}
    v_p([a, b, c])&= \max\{v_p(a), v_p(b), v_p(c)\}=r.
  \end{aligned}
\]
另一方面，
\[
\begin{aligned}
  v_p(a,b,c)&= \min\{v_p(a), v_p(b), v_p(c)\}=t,\\
  v_p(a,b)&= \min\{v_p(a), v_p(b)\}=s,\\
v_p(b,c)&= \min\{v_p(b), v_p(c)\}=t,\\
v_p(a,c)&= \min\{v_p(a), v_p(c)\}=t,
\end{aligned}
\]
从而
\[
  \begin{aligned}
    v_p\left(\frac{a b c(a, b, c)}{(a, b)(b, c)(c, a)}\right)&= 
v_p(a)+v_p(b)+v_p(c)+v_p((a, b, c)) \\
&\hspace{1.3em} - v_p((a, b)) -v_p((b, c)) -v_p((c, a))\\
&= r+s+t+t-s-t-t=r.
  \end{aligned}
\]
因此
\[
  v_p([a, b, c]) =r = v_p\left(\frac{a b c(a, b, c)}{(a, b)(b, c)(c, a)}\right).
\]
证毕。
\end{solution}

\begin{exercise}
  令$a_1, a_2, \cdots, a_s$为正整数。
证明：$[a_1, a_2, \cdots, a_s]=a_1a_2\cdots a_s$当且仅当$a_1, a_2, \cdots, a_s$两两互素。
\end{exercise}


\begin{proof}
  对任意的素数$p$, 
  \[
  \begin{aligned}
      v_p([a_1, a_2, \cdots, a_s])&= \max\{v_p(a_1),\cdots,v_p(a_s)\},\\
        v_p(a_1a_2\cdots a_s)&= v_p(a_1)+\cdots+v_p(a_s).
      \end{aligned}
\]
  我们有 $[a_1, a_2, \cdots, a_s]=a_1a_2\cdots a_s$当且仅当
  对每个素数$p$,
  \[
\max\{v_p(a_1),\cdots,v_p(a_s)\}=
v_p(a_1)+\cdots+v_p(a_s),
\]
当且仅当
对每个素数$p$, 至多一个$v_p(a_i)$非零，
当且仅当
  对每个素数$p$, 至多存在一个$a_i$使得$p\mid a_i$,
  亦即
  $a_1, a_2, \cdots, a_s$两两互素。
\end{proof}

\begin{exercise}
对任意整数 $a_{1}, a_{2}, \cdots, a_{s}$, 证明：
\[
a_{1} \ZZ \cap a_{2} \ZZ \cap \cdots \cap a_{s} \ZZ=\left[a_{1}, a_{2}, \cdots, a_{s}\right] \ZZ
\]
其中 $a \ZZ=\{a k \mid k \in \ZZ\}$.
\end{exercise}

\begin{solution}
  令$m=\left[a_{1}, a_{2}, \cdots, a_{s}\right]$. 由于任意的$a_i\mid m$,
  $m$的倍数是$a_i$的倍数，故$a_i\ZZ\supset m\ZZ$, 
  从而$\bigcap_{i=1}^s a_i\ZZ\supset m\ZZ$.
  反过来，若$c\in \bigcap_{i=1}^s a_i\ZZ$, 则$c\in a_i\ZZ$表明$c$为$a_i$的倍，对任意的$i$.
  从而$m\mid c$, 即$c\in m\ZZ$. 
  这就证明了$\bigcap_{i=1}^s a_i\ZZ\subset m\ZZ$.
  进而$\bigcap_{i=1}^s a_i\ZZ=m\ZZ$.
\end{solution}

\begin{exercise}
证明： 若 $p=2^{m}+1$ 是素数 $(m \geqslant 1)$, 则 $p=F_{n}=2^{2^{n}}+1$.
(称 $F_{n}$ 为第 $n$ 个 Fermat (费马) 数， 例如 $n=0,1,2,3,4$ 时， 分别求得 $F_{n}=3,5,17$,
257,65537 , 均为素数。)
\end{exercise}

\begin{solution}
  $m=1$时结论显然成立，设$m>1.$ 若$m$不是形如$2^n$, 则$m=pq$, 其中$p$是奇素数，$q\in \ZZ$.
  此时
  \[
    2^m+1=(2^{q})^p+1=(2^q)^p-(-1)^p=(2^q+1)\left( (2^q)^{p-1}+\cdots-2^q+1 \right)
  \]
是合数，与假设矛盾了。
这里注意到由于$(2^{q})^p+1>2^q+1$, $\left( (2^q)^{p-1}+\cdots-2^q+1 \right)>1$.
\end{solution}

\begin{exercise}
 [Euler(欧拉)] 试证明： 第 5 个 Fermat 数 $F_{5}=2^{25}+1$ 不是素数。

(Fermat 曾猜想 $F_{n}$ 均为素数 $(n \geqslant 0)$. 但 Euler 发现 $641 \mid F_{5}$. 目前已证明 $5 \leqslant n \leqslant 32$ 时 $F_{n}$均非素数， 尚未发现 $n \geqslant 5$ 时有素数 $F_{n}$, 现猜测均非素数。 1801 年 Gauss 证明了： 正 $N$ 边形能“用圆规直尺作图作出” 当且仅当 $N=2^{*} p_{1} \cdots p_{s}$, 其中 $p_{i}$ 为 Fermat 素数。 例如， $N=3,4$, $5,6,10,17$ 等。 )
\end{exercise}

\begin{exercise}
证明： 若 $M=a^{b}-1$ 是素数 $\left(a, b>1\right.$ ), 则 $M=M_{p}=2^{p}-1$ (某素数 $p$ ).
( $M_{p}$ 称为 Mersenne(梅森) 数， 不一定是素数， 例如 $M_{11}=23 \cdot 89$. 到 2015 年 9 月， 已知有 49 个 Mersenne 数 $M_{p}$ 为素数， 最大者是 $2^{74207281}-1$. )
\end{exercise}


\begin{exercise}
证明： 可写为 $4 k-1$ 形式的素数 (常称为 $4 k-1$ 型素数) 的个数是无穷的 ( $k$ 为整数).
\end{exercise}

\begin{exercise}
试证明： $4 n^{2}+1$ 的任一素数因子 $p$ 必可写为 $4 k+1$ 型 ( $k$ 为整数).
\end{exercise}

\begin{exercise}
证明： 可写为 $4 k+1$ 型的素数的个数是无穷的 ( $k$ 为整数).
\end{exercise}

\begin{exercise}
 证明： 若正整数 $m$ 不是完全平方数， 则 $\sqrt{m}$ 是无理数。
\end{exercise}

\begin{exercise}
 证明如下数不是整数 $(n \geqslant 2)$ :
\[
r_{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}
\]
\end{exercise}

\begin{exercise}
证明： 第 $n$ 个正素数 $p_{n} \leqslant 2^{2^{2-1}}$.
\end{exercise}

\begin{exercise}
记 $\pi(x)$ 为不超过 $x$ 的正素数个数， 证明： $\pi(x) \geqslant\left\lfloor\log _{2}\left(\log _{2} x\right)\right\rfloor+1$.
\end{exercise}

\begin{exercise}
证明： 可写为 $3 k-1$ 型的素数 ( $k$ 为整数) 的个数是无穷的。
(说明： 上述例子证明了 $4 k+3,4 k+1,3 k+2$ 型的素数均有无限多。 事实上， $a k+b$ 型素数均是无限多的 (其中 $a, b$ 互素， $k=1,2,3, \cdots$ ). 也可叙述为：算数序列 $\{a k+b\}(k=1$, $2, \cdots$ ) 中含有无限多素数。 这是著名的 Dirichlet(狄利克雷， 1837) 算术数列含素数定理。)
\end{exercise}

\begin{exercise}
证明：可写为 $6 k-1$ 型的素数 ( $k$ 为整数) 的个数是无穷的。
\end{exercise}

\begin{exercise}
证明： 整数 $n$ 为合数当且仅当有素因子 $p \leqslant \sqrt{n}$.
(因此， 我们要验证 $n$ 是素数， 只需验证素数 $p \leqslant \sqrt{n}$ 均非其因子。 这是很实用的检验素数的方法。 当 $n$ 为合数时， 这也是尝试因子分解的实用方法。)
\end{exercise}

\begin{exercise}
埃拉托色尼笕法 (sieve of Eratosthenes, 约公元前 276一约前 195) 是求出素数表的系统方法： 首先列出正整数表 $2,3,4, \cdots, N$. 然后从表中删去 2 的所有倍数 ( 2 除外), 再删去 3 的倍数 ( 3 除外), 等等， 直到删去素数 $p \leqslant \sqrt{n}$ 的所有倍数 ( $p$ 除外); 剩下的就是 2 到 $N$ 之间的素数表。 证明此笕法的正确性， 用此法作出 100 以内的素数表。
\end{exercise}

\begin{exercise}
  设$a_1, \cdots, a_s$为两两互素的正整数，且$a_1\cdots a_s=b^2$为平方数。
  证明所有$a_i$都是平方数。
\end{exercise}

\begin{solution}
  $a_i$为平方数相当于对任意的素数$p\mid a_i$, $v_p(a_i)$为偶数。
  由于$a_1, \cdots, a_s$两两互素, $p\nmid a_j$, 对$j\neq i$.
  这样
  \[
    v_p(a_i)=v_p(a_1\cdots a_s)=v_p(b^2)=2v_p(b)
  \]
  确为偶数。因此$a_i$为平方数。
\end{solution}


\section{线性 Diophantus 方程}

\begin{exercise}
求所有整数解： (1) $24 x+45 y=6$. (2) $167 x+23 y=1$.
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 由于$d=(24,45)=3\mid 6$, 所给方程有解。
      $24 x+45 y=6$两边除以$3$可得同解的Diophantine方程
      $8x+15y=2$. 注意到$8\times2+15\times(-1)=1$,  
      \[
        (x,y)=2\cdot(2,-1)=(4,-2)
      \]
      为$8x+15y=2$的一个解。
      进而由定理1知$24 x+45 y=6$的通解为
      \[
        (x,y)=(4-15k, -2+8k) \quad (k\in\ZZ).
      \]
    \item 由于$d=(167,23)=1\mid 1$, 所给方程有解。
      辗转相除可知$4\times 167-29\times 23=1$, 
      $(x,y)=(4,-29)$为一个解。
      进而由定理1知$167 x+23 y=1$的通解为
      \[
        (x,y)=(4-23k, -29+167k) \quad (k\in\ZZ).
\tag*{\qedhere}
      \]
  \end{enumerate}
\end{solution}

\begin{exercise}
求所有整数解： (1) $12 x+54 y+10 z=4$. (2) $54 x+39 y+12 z=3$.
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 注意到$(12,54)=6, (6,10)=2$, 我们把$12 x+54 y+10 z=4$改写成如下的方程组
      \[
        \begin{cases}
          12 x+54 y&= 6t,\\
          6t +10 z&= 4.
        \end{cases}
      \]
      $6t +10 z= 4$与$3t+5z=2$同解。
      $3t+5z=1$的一个解为$(t,z)=(2,-1)$, 故$3t+5z=2$
      的一个解为$(t,z)=(4,-2)$. 进而可知$3t+5z=2$的通解为
      \[
        (t,z)=(4-5k,-2+3k)\quad
      (k\in\ZZ).
    \]
      $12 x+54 y= 6t$与$2x+9y=t$同解。
      注意到$2\times(-4)+9=1$, 故
      \[
        (x,y)=t\cdot (-4, 1)=(-4t, t)
      \]
      是$2x+9y=t$的一个解。
      再代入$t=4-5k$, 进而可知通解为
      \[
        (x,y)=(-4(4-5k)-9l,(4-5k)+2l)\quad (l\in \ZZ).
      \]
      这样我们得
      \[
        (x,y,z)=(-16+20k-9l,4-5k+2l, -2+3k)\quad (k,l\in\ZZ).
      \]
      容易发现这就给出了$12 x+54 y+10 z=4$的通解。
    \item 注意到$(54,39)=3, (3,12)=3$, 我们把$54 x+39 y+12 z=3$改写成如下的方程组
      \[
        \begin{cases}
          54 x+39 y&= 3t,\\
          3t +12 z&= 3.
        \end{cases}
      \]
      $3t +12 z= 3$与$t+4z=1$同解。容易发现后面的方程的通解为
      \[
        (t,z)=(1-4k,k)\quad
      (k\in\ZZ).
    \]
      $54 x+39 y= 3t$与$18x+13y=t$同解。
      注意到$18\times(-5)+13\times 7=1$, 故
      \[
        (x,y)=t\cdot (-5, 7)=(-5t, 7t)
      \]
      是$18x+13y=t$的一个解。
      再代入$t=1-4k$, 进而可知通解为
      \[
        (x,y)=(-5(1-4k)-13l,7(1-4k)+18l)\quad (l\in \ZZ).
      \]
      这样我们得
      \[
        (x,y,z)=(-5+20k-13l,7-28k+18l, k)\quad (k,l\in\ZZ).
      \]
      容易发现这就给出了$54 x+39 y+12 z=3$的通解。
\qedhere
  \end{enumerate}
\end{solution}

\begin{exercise}
设 $a, b$ 为正整数， $d=(a, b)$. 证明： 当 $k d>a b$ 时， $k d$ 均可表为 $a x+b y$ 形式 $(x, y$ 为正整数).
\end{exercise}

\begin{exercise}
设 $a_{1}, \cdots, a_{1}$ 为互素正整数， 且 $\left(a_{s}-1\right)\left(a_{1}+\cdots+a_{s-1}\right) \leqslant n$, 证明： $a_{1} x_{1}+\cdots+a_{s} x_{s}=n$有非负整数解。
\end{exercise}

\begin{exercise}
按如下方法， 不用辗转相除， 证明整数的 Bézout 等式。

\begin{enumerate}[(1)]
\item 设 $a, b$ 为整数， $M=\{x a+y b \mid x, y \in \ZZ\}$. 设 $d=s a+t b$ 是 $M$ 中最小正整数 (自然数
的良序性). 设带余除法 $a=d q+r(0 \leqslant r<d), b=d q_{2}+r_{2}\left(0 \leqslant r_{2}<d\right)$, 则 $r, r_{2} \in M$.

\item%(2)
由 (1) 知 $d=s a+t b$ 是 $a, b$ 的公因子， 从而是最大公因子。
\end{enumerate}
\end{exercise}

\begin{exercise}
[Bézout 系数] 设 $d=(a, b), a^{\prime}=a / d, b^{\prime}=b / d$. Bézout 等式 $u a+v b=d$ 的系数对 $u, v$不是唯一的， 两个系数对之间有何关系? 求证：恰有两个系数对满足：
\[
 |u| <\left|b^{\prime}\right|, \quad|v|<\left|a^{\prime}\right| .
\]
\end{exercise}

\begin{exercise}
[Bézout 系数] 对整数 $a, b$ 辗转相除 (如定理 2 前， $r_{s+1}=0$ ). 证明：

\begin{enumerate}[(1)]
\item 各余数 $r_{k}(k=0,1, \cdots, s)$ 满足
\[
v_{k} a-u_{k} b=(-1)^{k} r_{k+1}
\]
其中
\[
\left\{\begin{array}{lll}
u_{-2}=0, & u_{-1}=1, & u_{k}=q_{k} u_{k-1}+u_{k-2} \\
v_{-2}=1, & v_{-1}=0, & v_{k}=q_{k} v_{k-1}+v_{k-2}
\end{array}\right.
\]
故 Bézout 等式系数对为
\[
(u, v)=\left(v_{s-1},-u_{s-1}\right)(-1)^{s-1}
\]
(当 $r_{s}$ 是辗转相除最后非零余数).

\item%(2)
$u_{k} v_{k-1}-u_{k-1} v_{k}=(-1)^{k-1}$, 特别知 $\left(u_{k}, v_{k}\right)=1$.

\item%(3)
$a / b=u_{s} / v_{s}$ (既约分数) $, u_{1}= \pm b / d, \quad v_{s}= \pm a / d$.

\item%(4)
当 $a, b$ 为正整数时， $|u|=\left|v_{s-1}\right|<a / d,|v|=\left|u_{s-1}\right|<b / d$. 故辗转相除得到的 Bézout 系数对 ((1) 中) 是绝对值最小的两个系数对之一。
\end{enumerate}
\end{exercise}

\section{多项式的分解}

\begin{exercise}
求 $d(X)=(f(X), g(X))$ 及其 Bézout 等式：

\begin{enumerate}[(1)]
\item $f(X)=X^{5}+3 X^{4}+X^{3}+X^{2}+3 X+1, \quad g(X)=X^{4}+2 X^{3}+X+2$.

\item%(2)
$f(X)=X^{5}+X^{4}-X^{3}-2 X^{2}+X, \quad g(X)=X^{4}+2 X^{3}-3 X$.
\end{enumerate}
\end{exercise}


\begin{exercise}
求证： $\frac{a^{3}+2 a}{a^{4}+3 a^{2}+1}$ 为既约分数 $(a \in \ZZ)$.
\end{exercise}

\begin{exercise}
证明： 在 Bézout 等式 $u(X) f(X)+v(X) g(X)=d(X)$ 中， 可选取 Bézout 系数 $u, v$ 使

\[
\operatorname{deg} u<\operatorname{deg}(g / d), \operatorname{deg} v<\operatorname{deg}(f / d)
\]
\end{exercise}

\begin{exercise}
试求 $f(X)$, 使得 $f(X)$ 除以 $(X+1)^{2}$ 余 $X, f(X)$ 除以 $(X-1)^{2}$ 余 1 .
\end{exercise}

\begin{exercise}
求最低次数多项式 $f(x)$ 使得

\[
f(k)=k^{5}+5 k \quad(k=1,2,3,4,5)
\]
\end{exercise}

\begin{exercise}
求如下多项式的所有复 (数)根， 并在复数域和实数域上分解它们：
\[
X^{n}+1, \quad X^{n}-a, \quad X^{n}+b
\]
  
\end{exercise}

\begin{exercise}
证明： (Lagrange(拉格朗日)插值公式) 设 $f(X)$ 为域 $F$ 上多项式， 次数小于 $n$, 且在 $n$ 个互异点 $a_{1}, \cdots, a_{n} \in F$ 取值为 $b_{1}, \cdots, b_{n}$, 则
\[
f(X)=\sum_{i=1}^{n} b_{i} \frac{\left(X-a_{1}\right) \cdots\left(X-a_{i-1}\right)\left(X-a_{i+1}\right) \cdots\left(X-a_{n}\right)}{\left(a_{i}-a_{1}\right) \cdots\left(a_{i}-a_{i-1}\right)\left(a_{i}-a_{i+1}\right) \cdots\left(a_{i}-a_{n}\right)}
\]
\end{exercise}

\begin{exercise}
设 $F(\subset \mathbb{C})$ 为数域， $p(X) \in F[X]$ 不可约， $f(X) \in F[X]$, 如果 $p(X)^{m} \mid f(X)$, 而 $p(X)^{m+1} X f(X)$, 则称 $p(X)$ 是 $f(X)$ 的 $m$ 重因子， 记为 $p(X)^{m} \\mid  f(X) \cdot m \geqslant 2$ 时称 $p(X)$ 为重因子， $m=1$ 时称 $p(X)$ 为单因子。 与上述定理类似证明：

\begin{enumerate}[(1)]
\item $p(X)$ 为 $f(X)$ 的重因子当且仅当 $p(X)$ 为 $f(X)$ 和 $f^{\prime}(X)$ 的公因子。

\item%(2)
若 $\left(f(X), f^{\prime}(X)\right)=1$, 则 $f(X)$ 无重因子。 反之亦然。
\end{enumerate}
\end{exercise}

\begin{exercise}
证明： 不同的 Fermat 数 $F_{n}=2^{2^{n}}+1$ 互素 ( $n$ 为非负整数). 由此推论出： 素数有无限多。
\end{exercise}

\begin{exercise}
证明：不存在整系数多项式 $f(x)$ (非常数) 使 $f(n)$ 对所有整数 $n$ 都是素数， 或对充分大的 $n$ 都是素数。
\end{exercise}

\begin{exercise}
将分母不超过自然数 $n$ 的既约真分数由小到大排列， $0 / 1$ 为首， $1 / 1$ 为尾， 称为 Farey(法里) 序列， 记为 $\Phi_{n}$. 例如
\[
\Phi_{1}=\{0 / 1,1 / 1\}, \quad \Phi_{2}=\{0 / 1,1 / 2,1 / 1\}, \quad \Phi_{3}=\{0 / 1,1 / 3,1 / 2,2 / 3,1 / 1\}
\]
显然， 左右对称， $1 / 2$ 为中心。 $\Phi_{n}$ 包含 $\Phi_{n-1}$, 而多出 $k / n,(k, n)=1$. 故 $\left|\Phi_{n}\right|=\left|\Phi_{n-1}\right|+$ $\varphi(n)$. Farey 序列与连分数、格伦、共鸣与音律、Riemann(黎曼)假设等均关系密切。 证明以下各命题：

命题 A: $\Phi_{n}$ 中相邻两项 $h / k$ 与 $h^{\prime} / k^{\prime}$ 满足 $k+k^{\prime}>n$.

命题 B： $\Phi_{n}$ 中相邻两项 $h / k$ 与 $h^{\prime} / k^{\prime}$ 的分母不同 $(n>1$ 时 $)$.

命题 C: $\Phi_{n}$ 中相邻两项 $h / k$ 与 $h^{\prime} / k^{\prime}$ 之差为 $1 / k k^{\prime}$, 即 $k h^{\prime}-h k^{\prime}=1$.

命题 D: $\Phi_{n}$ 中相邻三项 $h / k, h^{\prime \prime} / k^{\prime \prime}, h^{\prime} / k^{\prime}$ 的中项为 $\frac{h^{\prime \prime}}{k^{\prime \prime}}=\frac{h+h^{\prime}}{k+k^{\prime}}$ (中项公式， mediant formula).

命题 E: $\Phi_{n}$ 中 $h / k$ 的后邻项 $h^{\prime} / k^{\prime}$ 求法： 满足 $k h^{\prime}-h k^{\prime}=1$ 且使 $0 \leqslant k^{\prime}<k$.
\end{exercise}

\section{连分数及其应用}


  
\begin{exercise}
将 $\sqrt{2}, \sqrt{3}, \sqrt{6}, \sqrt{19}$, 和 $(3+\sqrt{13}) / 2$ 展开为连分数。
\end{exercise}

\begin{solution}
  要把$\sqrt{2}$展开为连分数，我们写：
  \[
    \sqrt{2}=1+(\sqrt{2}-1),\quad \frac{1}{\sqrt{2}-1}=\sqrt{2}+1 = 2+(\sqrt{2}-1).
  \]
  注意到小数部分已循环，我们知
  \[
    \sqrt{2}=[1;2,2,\cdots]=[1;\bar{2}].
  \]

  要把$\sqrt{3}$展开为连分数，我们写：
  \[
      \sqrt{3}=1+(\sqrt{3}-1),\quad \frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2}=1+\frac{\sqrt{3}-1}{2},\quad
      \frac{2}{\sqrt{3}-1}=\sqrt{3}+1=2+(\sqrt{3}-1).
  \]
  注意到小数部分已循环，我们知
  \[
    \sqrt{3}=[1;1,2,1,2,\cdots]=[1;\overline{1,2}].
  \]

要把$(3+\sqrt{13}) / 2$展开为连分数，我们写：
\[
  \frac{3+\sqrt{13}}{2}=3+\frac{\sqrt{13}-3}{2},\quad
  \frac{2}{\sqrt{13}-3}=\frac{\sqrt{13}+3}{2}=3+\frac{\sqrt{13}-3}{2}.
\]
  注意到小数部分已循环，我们知
  \[
    \frac{3+\sqrt{13}}{2}=[3;3,3,\cdots]=[3;\bar{3}].
\tag*{\qedhere}
  \]
\end{solution}

\begin{exercise}
求 $(1+\sqrt{5}) / 2$ 的连分数和第 $n$ 个渐近分数， 证明其分母恰为 Fibonacci(斐波那契) 数列 $\left\{v_{i}\right\}$ (即满足 $v_{i+1}=v_{i}+v_{i-1}, v_{1}=v_{2}=1$ ).
\end{exercise}

\begin{solution}
  容易发现$\frac{1+\sqrt{5}}{2}$的连分数展开为$\frac{1+\sqrt{5}}{2}=[1;\bar{1}]$.
  这样由定理1知$q_0=1,q_1=1,q_n=q_{n-1}+q_{n-2}$.
  因此分母恰好构成Fibonacci数列。
\end{solution}

\begin{exercise}
将 $\sqrt{s^{2}+r}$ 展开为连分数， 其中 $r \mid 4 s$, 且 $s, r \in \ZZ,-s<r<4(s+1) / 3$.
\end{exercise}

  \begin{exercise}
[阴历大小月] 阴历中的大、小月 (各为 $30 、 29$ 天) 应如何分布?
\end{exercise}

\begin{exercise}
[沙罗周期]
  日食和月食的发生是由于太阳、月球、地球运行到几乎一条直线上。 故日月食发生的条件是：朔月或望月时 (即月亮最亏或最圆时), 且月球几乎在黄道平面内 (即月球在黄道和白道的两个交点附近). 朔望月的周期为 29.530588 天， 月球穿越黄道平面的周期 (交点月)是 27.212220 天。 试证明日、月食发生的沙罗周期 (Saros) 为 223 个朔望月 (synodic months), 约 6585.3211 天， 即 18 年又 $11 \frac{1}{3}$ 天(未计闰年).
\end{exercise}

\begin{exercise}
[火星大冲] 火星最亮和离地球最近的一年， 称为火星的大冲年。 按照地球公转周期为 365.25 天， 火星周期为 687 天， 试证明火星大冲每隔 15 年一次。
\end{exercise}

\begin{exercise}
如果采用“五度相生四十一律”, 试计算误差 “Pythagoras 微差” (用音分表示). 此时 $\mathrm{G}$ 是第几个(小)音级?
\end{exercise}

\begin{exercise}
正实数 $\alpha$ 与其倒数 $\frac{1}{\alpha}$ 的连分数有何关系? 为什么?
\end{exercise}

\begin{solution}
  若$\alpha=1$, $\alpha=\frac{1}{\alpha}$的连分数都是$[1]$.
  否则，不妨设$0<\alpha<1$. 要把$\alpha$展开为连分数，我们写
  \[
    \alpha=0+\alpha, \quad \alpha=\cdots.
  \]
  由此可知，若$\alpha$展开成连分数为$\alpha=[a_0;a_1,a_2\cdots]$, 则
  $\frac{1}{\alpha}=[0;a_0,a_1,a_2,\cdots]$.
\end{solution}

\begin{exercise}
求 $[1,1,1,1, \cdots],[2,2,2,2, \cdots]$.
\end{exercise}

\begin{solution}
  在练习2中我们已知$\frac{1+\sqrt{5}}{2}$的连分数展开为$[1;1,1,1, \cdots]$.
  故$[1;1,1,1, \cdots]=\frac{1+\sqrt{5}}{2}$.

  在练习1中我们已知$\sqrt{2}$的连分数展开为$[1;2,2,2, \cdots]$.
  这样$\sqrt{2}+1$的连分数展开为$[2;2,2,2, \cdots]$.
  因此$[2;2,2,2, \cdots]=\sqrt{2}+1$. 
%
%  由定理1知渐进分数的分子和分母满足：
%  \[
%    \begin{aligned}
%      p_0=2, \quad p_1=5, \quad p_n=2p_{n-1}+p_{n-2};\\
%      q_0=1,\quad  q_1=2, \quad q_n=2q_{n-1}+q_{n-2}.
%    \end{aligned}
%  \]
%  令$\alpha, \beta$为$x^2-2x-1=0$的两个根，比如$\alpha=1+\sqrt{2}, \beta=1-\sqrt{2}$.
%  那么$\alpha+\beta=2, \alpha\beta=-1$. 从而
%  \[
%  \begin{aligned}
%      p_n-\alpha p_{n-1}&=  \beta(p_{n-1}-\alpha p_{n-2}),\\
%      q_n-\alpha q_{n-1}&=  \beta(q_{n-1}-\alpha q_{n-2}).
%    \end{aligned}
%\]
%对$n\geqslant 1$, 令$a_n=p_n-\alpha p_{n-1}, b_n=q_n-\alpha q_{n-1}$. 那么
%$a_1=5-2\alpha=$
%$a_n=\beta a_{n-1}, b_n=\beta b_{n-1}$, 从而
%\[
%  \begin{aligned}
%    a_n&= \beta^{n-1}a_1=\beta^{n-1}(p_1-\alpha p_0), 
%  \end{aligned}
%\]
%  因此
%  \[
%    p_n=a_{n+1}=\frac{\left( \frac{1+\sqrt{5}}{2} \right)^{n+1}-\left( \frac{1-\sqrt{5}}{2} \right)^{n+1}}{\sqrt{5}},\quad
%    q_n=a_n=\frac{\left( \frac{1+\sqrt{5}}{2} \right)^n-\left( \frac{1-\sqrt{5}}{2} \right)^n}{\sqrt{5}}.
%  \]
%  这样第$n$个渐进分数为
%  \[
%    \frac{p_n}{q_n}=
%  \]
\end{solution}



